package com.zhugang.week13.linkedlist;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: hasCycel
 * @author: chanzhugang
 * @create: 2022/09/09 17:16
 */
public class HasCycle {

    /**
     * 141 环形链表
     * https://leetcode.cn/problems/linked-list-cycle/
     * 时间复杂度：O(n)，最坏遍历n个节点
     * 空间复杂度：O(n)，最坏情况需要把每个节点插入到哈希表
     *
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // Set(底层是Map)去重，效率不是很高
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (!set.add(p)) {
                return true;
            }
           /* if (set.contains(p)) {
                // contains函数耗时
                return true;
            }
            set.add(p);*/
            p = p.next;
        }
        return false;
    }

    public boolean hasCycle2(ListNode head) {
        // 推荐：快慢指针
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null && fast != slow) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if (fast == slow) {
            return true;
        }
        return false;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        HashMap<Object, Object> objectObjectHashMap = new HashMap<>();
    }
}